#!/usr/bin/env python
# encoding: utf-8
'''
@author: Excelsiorly
@license: (C) Copyright 2022, All Rights Reserved.
@contact: excelsiorly@qq.com
@file: 047. 全排列 II.py
@time: 2022/1/21 13:15
@desc: https://leetcode-cn.com/problems/permutations-ii/
> 给定一个可包含重复数字的序列 nums ，按任意顺序返回所有不重复的全排列。

@解题思路：
    1. 排序
    2. 重复元素就先排序
    3. Ot(n*n!), Os(n)
'''
class Solution(object):
    def permuteUnique(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        n = len(nums)
        nums.sort()
        visited = [False]*n
        def backtrack(path, length):
            if length==n:
                res.append(path)
                return
            for i in range(n):
                # 跳过访问过的，且剪枝
                if visited[i] or (i>0 and nums[i]==nums[i-1] and not visited[i-1]): continue
                visited[i] = True
                backtrack(path+[nums[i]], length+1)
                visited[i] = False
        res = []
        backtrack([], 0)
        return res

if __name__ == '__main__':
    res = Solution().permuteUnique([1,1,2])
    print(res)